兴趣度度量指标 常见的6_第六讲(关联规则分析).ppt 54页

兴趣度度量指标 常见的6_第六讲(关联规则分析).ppt 54页

多层关联搜索策略（寻找频繁项集的方法） 支持递减的多层关联规则方法可以使用三种搜索策略： 逐层独立（太松散）：全宽搜索，每个第一层的数据只与当前层的最小支持度进行比较。没有用于剪枝的频繁项集的背景知识。优点是方法简单，缺点是条件过于宽松，导致需要调查底层大量的不频繁数据，浪费计算。 , 极低效率级别的跨单项过滤方法（妥协）：第i级别的项目被检查当且仅当它在（i-1）级别的父节点上频繁，即即满足最小支持度要求，缺点是有时父节点不满足当前层的最小支持度，但其子节点满足其子节点的最小支持度。省略检查层 过滤（太严格）：检查第 i 层的 k 项集，当且仅当它在 (i-1) ），这种方法限制性很强（很少有频繁的模式满足这个条件），导致很多有趣的模式没有被调查，因此没有被探索。三种搜索策略相对逐层独立，条件宽松，这可能会导致调查大量不常见的 i tem- -k item set过滤策略限制太强了。它是子级交叉单项过滤策略之间的折衷，只允许检查频繁的k-项集，但仍然可能失去低级频繁项控制的跨级单项过滤策略。如何修改和改进被入侵的过滤策略呢？手动设置一个层转移阈值，用于将比较频繁的项目转移到下层。

即满足层级转移阈值，不满足最小支持度阈值的的子项允许检查（虽然支持度为10%，但不满足层12的最小支持度） %，但它满足阈值 8%，那么我们不检查而是允许检查他们的孩子 Lap 和 Desk） 用户有更多的灵活性在多概念层面上进一步控制挖掘过程，同时减少调查和生成无意义关联 [=10%] [=6%] [=4%] 第一级 = 12% t = 8% 第二级 = 3% 在挖掘多级关联规则时检查冗余多级关联规则时，由于对于上下级的“祖先”关系，祖先后代是超集关系，找到的一些规则会是多余的。例如：=> b/w [sup=8%, con=70%] (1)IBM => b/w [sup=2%, con =72%] (2)在上面的例子中，我们知道第一条规则是第二条规则的“祖先”，如果满足条件：IBM在其中的比例是（1/4)刚好等于（2%除以8%），那么我们认为规则（2)无用，即多余，因为已知条件“祖先”和“规则1”可以推导出其“后代”规则（2).

即：如果将规则(2))中的项替换为其概念层次结构中的“祖先”，则可以得到(1)，且(1))的支持度和置信度接近“期望”值，则（1)是多余的。多维关联规则-基本概念单维关联规则：buys(X, “milk”) = buys(X, “”)，只涉及单-维度多维关联规则：涉及两个或多个维度或谓词的关联规则。第一类：维度之间的关联规则：不包含重复谓词age(X,"19-25") ∧(X,"") =>buys(X,"Coke") 第二种：混合维关联规则：包含多次出现的某个谓词 age(X,"19-25") ∧buys(X, “”) => buys(X, “可乐”）根据属性值的特点，将多维关联规则分为分类属性和定量属性。不同的价值观，而且价值观是无序的（例如，包括学生、教师、医生等）。职业和个人之间没有有序的关系（数量有限） 数量属性：数值，数值之间有隐含的顺序（比如年龄是19-25岁，但是之间有无数的数值） 19-25 可挖掘和排序）挖掘多维关联规则---基础技术 单维关联规则挖掘频繁项集，而在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。

k-谓词集是一个包含k个连接谓词的集合。例如：{,,milk}是一个buys谓词下的频繁项集，属于单维挖掘，而{age,,buys}是一个3谓词集，属于多维挖掘技术用于挖掘多维关联规则。可以量化 属性的处理分为三种基本方法： 1. 量化属性静态离散 使用预定义的概念层对量化属性进行静态离散（例如定义年龄上的概念层：年轻/中年/老年，离散化无穷大年龄数据转化为这三个概念）2.量化关联规则根据数据的分布将量化属性离散成“盒子”，类似于之前的装箱技术3.基于距离的关联规则考虑数据点量化属性之间的距离动态离散化，使数据更符合挖掘需求。多维关联规则挖掘方法（1）-- 使用预定义的概念进行层次化，并在挖掘前进行离散化的数值属性的值替换为一个区间。如果任务相关的数据存在于一个关系型数据库，需要k或者k+1次表扫描才能找到所有的频繁k-谓词集（比如age//购买这三个维度之间的频繁3-谓词集来查找，需要扫描数据3或4倍）与关系数据库技术不同，数据立方体技术存储多维数据，非常适合挖掘多维关联规则 n维立方体单元 用于存储对应n个谓词集的计数或支持度（At这一次，我们不再存储第 2 章中的汇总数据，而是存储满足此谓词集条件的出现次数或支持度），0-D 平方的事务总数用于存储与任务相关的数据！如果包含感兴趣维度的数据立方体已经存在并被物化，则挖掘速度会很快，同时它可以利用以下性质：频繁谓词集的每个子集也必须是频繁的，例如：如果3 谓词集是频繁的 (age,,buys)，那么 (age,)\(age,buys)\(,buys) 也一定是频繁的。

() (age) () (buys) (age,) (age,buys) (,buys) (age,,buys) 多维关联规则挖掘方法（2）----挖掘量化关联规则 A. 在量化关联规则中，数值属性会根据挖掘任务的一定挖掘标准动态离散化，例如：最大化挖掘规则的置信度和紧凑性。为了简化对量化关联规则的讨论挖掘，我们将重点关注类似于以下形式的二维量化关联规则：??Acat（两个量化属性和一个分类属性之间的关联） 例如：age(X,”30-39”)?(X, ”42K-48K”)?Buys(X,“high TV”) 求上述二维定量关联规则的方法：关联规则聚类系统（ARCS）是一种源自图像处理的模式识别技术，它映射满足要求的定量属性对。设置分类二维网格上的属性条件，然后通过搜索网格点的簇生成关联规则。多维关联规则挖掘方法（2）---挖掘定量关联规则。ARCS过程中的步骤包括1.（根据不同的方法创建一个二维数组）。这一步的目的是减少量化属性对应的巨量值的数量，从而控制二维网格的大小和等宽（将变量的取值范围划分为k个等宽的区间，并且每个区间作为一个bin）等距bins（变量对象根据数量平均分为k个区间，每个区间被视为一个bin）基于 （每个bin中的元组必须符合一致分布) 2. 找出通过扫描频繁谓词集的形成的二维数组，找到满足最小支持度和置信度的频繁谓词集多维关联规则挖掘方法(2）----关联规则集群ng (ARCS).C13.关联规则聚类将上一步得到的强关联规则映射到二维网格上，使用聚合类算法，扫描网格，搜索规则矩形聚类（借用聚类算法在图形处理，聚类是通过合并相邻的矩形来实现的：如果两个相邻的矩形满足最小支持度和置信度，我们就合并它们）多维关联规则挖掘方法（2）---- Rule (ARCS)。 C2 挖掘出的关联规则左侧只能是量化属性（非量化属性，坐标定位是不可能的） 规则左侧只能有两个量化属性（受限于我们使用的二维网格）。如果使用3-D和4-D网格，即使量化属性达到3、4，计算量也很大，呈指数级增长，方法的适应性有限并得到改进：一种不是基于网格的技术，但可以找到更通用的关联规则，其中任意数量的量化属性和分类属性可以出现在规则的两端（现在数字数据挖掘技术已经发展到可以挖掘任意数量的量化属性和分类属性，它可以出现在规则左右两侧的任意组合）这项新技术是基于动态划分等深度bins，它使用根据完整性度量的部分进行聚类多维关联规则挖掘方法（2）—the ARCS.C3多维关联规则挖掘方法的限制（3）------挖掘基于距离的关联规则等宽划分会非常接近 将值分开，并创建e 一个没有数据的区间，差评！等深划分把很远的值放在一个组里，差评！基于距离的关联规则挖掘考虑属性值的接近度，紧跟区间数据语义，允许相似值（等宽/等深/基于距离划分，距离范围分别为61/46/8） ，方法3除法间隔短，元素密集，这让我们的计算更加注重有意义间隔的范围），赞！基于距离的关联规则挖掘的两遍扫描算法：1.使用聚类寻找区间或集群（数据分布的区间或集群）2.搜索频繁一起出现的集群组，获得基于距离的关联规则@经过k13@两步扫描后，我们将原始数据映射到一个非常窄的聚类组，然后挖掘关联规则。由于前两种方法没有考虑数据点或区间之间的相对距离，方法并不总是能够密切跟踪区间数据。语义，在下面的例子中，等深等宽的分区数据并不理想！关联规则的兴趣度量（一种结合主观和客观度量的方法） 两个流行度量的客观度量。支持置信度的主观测量。最终，只有用户才能判断一个规则是否有趣，这个判断是主观的。不同的用户是不同的；通常一个规则（模式）被认为是有趣的，如果：它是出乎意料的、新颖的和可操作的，在挖掘关联规则后可以转化为结果（用户可以使用规则做某些事情） 哪些规则是用户感兴趣的？强关联规则有趣吗？连挖矿的强关联规则都对吗？强关联规则批判（1）例1：（&Yu，1998年发表的PODS文章）5000名学生中兴趣度度量指标，3000名打篮球兴趣度度量指标，3750名喝燕麦，2000名既打篮球又喝燕麦粥的学生可以挖掘出基于关联规则的关联规则在这个数据上：打篮球的学生倾向于喝燕麦片，支持度为40%，置信度为66.7%。

那就是：打篮球=>喝燕麦片[40%, 66.7%] 但是打篮球=>喝燕麦片[40%, 66.7%]是错误的，因为所有学生的比例在中国喝燕麦片的比例为 75%，高于篮球学生的 66.7%。这说明打篮球和喝燕麦片的关系不是正相关，而是负相关，不存在演绎关系。相反，我们可以推断打篮球=> 不喝麦片[20%, 33.3%]。这条规则比上面的要准确得多。虽然支持度和置信度低了很多，但还是符合实际比赛的。关联规则的批判（2）例2：从上面的数据可以得出，buys(X, “”) => buys(X, “”) [40%, 60%] 但实际上，数买过录像带的人是75%，超过60%；其实录像带和游戏是负相关的，也就是买完游戏就不愿意再买录像带了，但是数据挖掘得出的规律正好相反，也就是说，他们很可能在购买游戏后购买录像带。关联规则A => B的置信度具有欺骗性，它只给出了A和B的条件概率的估计，并没有衡量A和B的实际实力A和B之间的含义。从相关分析到相关分析我们需要一个事件的度量当项目集A的出现与项目集B的出现无关时，P(A∪B)=P(A)P(B) ,即B=1,表示A和B不相关,,B>1表示A和B正相关,,B买(X,"")Y,W取属性值赋值分别对谓词变量P1和P2进行编辑，元规则形成了用户想要探索的假设，并且系统查找与元规则匹配的规则，例如：age(X, "30-39" ）？ （X，“42K-60K”）？ Buys(X, "") 元规则引导的关联规则挖掘（2）假设我们希望挖掘的元规则的形式是：P1∧P2∧…∧Pl=>Q1∧Q2∧…∧Qr设置元规则中的谓词个数为p=l+r，然后找出哪些匹配模板关联规则需要以下两步： 找到所有频繁的p-谓词集Lp 计算中l-谓词子集的支持度Lp，然后计算由Lp导出的规则的置信度，数据立方体具有存储多维度值的能力，因此非常适合挖掘上述多谓词关联规则。 n维数据立方体(n>=p)可以使用以下步骤： 扫描pD立方体，将每个单元的计数最小化 比较支持计数得到Lp，因为pD立方体中存储的不是一个数据的汇总，而是p维谓词出现概率的计数。

调查 lD 立方体并返回与元规则匹配的强关联规则。由附加规则约束引导的挖掘。在数据挖掘中，与元规则一起使用的约束包括集合/子集关系、变量初始化和聚合函数等，它们将使挖掘过程更加有效。例如DMQL表示的数据挖掘任务如下： mine as (1、指定挖掘知识类型) (C, _,"") ∧+(C, ?{I},{ S}) => + (C, ?{J},{T}) (2、 使用元规则来表示我想挖掘的规则的模式) from (3、 指定相关数据集) S. year=1999 和T.year=1999 和 I.=J。 by C, I. sum(I.)=500 (4, 指定一系列约束) with =1% with =50% (5, ) 挖掘过程中使用的规则约束 在正常的数据挖掘中兴趣度度量指标，知识类型和在挖掘之前使用数据约束，在挖掘之后使用其他约束来过滤规则，但这使得挖掘过程非常低效。

在挖掘过程中可以使用哪些类型的规则约束来缩小规则搜索空间？对于频繁项集挖掘，挖掘过程中使用的约束包括以下五种：反单调、单调、简洁、可变换、不可变换、反单调和单调约束。如果一个项集不满足规则约束，那么它的任何超集都不可能满足这个约束；具有此属性的规则称为反单调，例如算法。性质：任何不常见项集的所有超集也是不常见的。如果一个项集满足这个约束，它的所有超集也满足这个约束；具有此属性的规则称为单调规则。简洁性约束 约束是简洁的。如果我们可以列出并且只列出所有确保满足约束的集合；使用简洁性约束，我们可以在计数之前进行修剪，从而避免测试方法的过度开销。可转换和不可转换的约束。可变换约束：有些约束不属于前三类，但是如果项集中的项按照特定的顺序排列，对于频繁项集挖掘的整个过程，约束可能会变得单调或单调 反单调甚至简洁例如： avg(I.) [20%, 60%] 找到下层关联规则： -> [10%, 50%] 跨级关联规则，如越过概念层边界的规则。 : => b/w 跨层关联规则应该使用下层的最小支持度而不是上层。

根据每一层使用的最小支持度阈值指标，多层关联挖掘方法分为：一致支持度VS。递减支持 统一支持：对所有层使用一致的最小支持 优点：搜索时容易采用优化策略，即如果某项不满足最小支持度，则可以搜索其所有子项。简单高效！缺点：设置最小支持度值太难，缺点明显大于优点。太高：会丢弃出现在较低抽象层的有意义的关联规则。太低：会在高层产生太多无趣的规则。减少支持：在较​​低层使用减少的最小支持抽象层。 , 越小对应的最小支持度[=10%] [=6%] [=4%] 第一层= 5% = 5% 第二层= 3%

Tags：兴趣度度量指标